import collections


class Solution(object):
    def countSubTrees(self, n, edges, labels):
        d = collections.defaultdict(set)
        for u, v in edges:
            d[u].add(v)
            d[v].add(u)
        p = [0] * n
        p[0] = 1
        self.ans = [0] * n

        def dfs(id):
            val = ord(labels[id]) - ord('a')
            out = [0] * 26
            out[val] = 1
            for v in d[id]:
                if not p[v]:
                    p[v] = 1
                    r = dfs(v)
                    for i in range(26):
                        out[i] += r[i]
            self.ans[id] = out[val]
            return out

        dfs(0)

        return self.ans
